package com.clstu.binarysorttree;

/**
 * 研究二叉排序树
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        //测试
        int[] arr = {9,8,7,6,5,4,3,2,1,2,3,4,5,6,7,8,9};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        for (int i = 0; i < arr.length-12; i++) {
            binarySortTree.delete(arr[i]);
        }
        binarySortTree.infixOrder();//1,2,3,4,5,6,7,8,9
    }
}
/**
 * 排序二叉树类
 */
class BinarySortTree{
    private Node root;
    //构造器
    public BinarySortTree(Node root){
        this.root = root;
    }

    //无参构造器
    public BinarySortTree(){}

    //编写方法添加节点
    public void add(Node node){
        //先判断是否树空
        if(root == null){
            root = node;
            return;
        }
        //添加
        root.add(node);
    }

    //不足之处:当二叉树种有两个节点值相同时删不掉(通过方法重置,指定节点删除的方式解决掉了这个问题!!)
    //编写方法删除二叉树的节点(根据值),使删除后仍然使二叉树有序
    public void delete(int delVal){
        //思路分析:
        //因为不能自我删除,需要编写方法找到目标节点的父节点
        //因为要删除的节点可能会有多种不同的情况,要分别分析
        //分3种,1.叶子节点 2.只有一边有子树 3.两边都有子节点
        //先遍历找到target和它的父节点
        Node target = searchNode(delVal);
        Node parent = getParent(delVal);
        //先判断是否找到要删除的节点
        if(target == null){
            System.out.println("删除失败.节点不存在");
            return;
        }
        //如果要删除的节点是根节点
        if(parent == null){
            //让右边的最小值来代替自己
            if(target.right!=null) {
                int i = deleteMin(target.right);
                Node newTarget = new Node(i);
                newTarget.left = target.left;
                newTarget.right = target.right;
            }else {
                root = root.left;
            }
            return;
        }
        //如果值叶子节点
        if(target.left==null&&target.right==null){
            if(parent.left == target){
                parent.left = null;
            }else{
                parent.right = null;
            }
            return;
        }
        //如果是有两个子树的节点
        if(target.left!=null && target.right!=null){
            //让右边的最小值来代替target
            int i = deleteMin(target.right);
            Node newTarget = new Node(i);
            if(parent.left == target){
                parent.left = newTarget;
            }else {
                parent.right = newTarget;
            }
            newTarget.left = target.left;
            newTarget.right = target.right;
            return;
        }
        //否则就是只有一颗子树的情况
        if(parent.left == target){
            if(target.left != null){
                parent.left = target.left;
            }else {
                parent.left = target.right;
            }
        }else {
            if(target.left!=null){
                parent.right = target.left;
            }else {
                parent.right = target.right;
            }
        }
    }

    //编写方法,根据传入的节点直接删除该节点
    public void delete(Node target){
        //找到它的父节点
        Node parent = getParent(target);
        //如果值叶子节点
        if(target.left==null&&target.right==null){
            if(parent.left == target){
                parent.left = null;
            }else{
                parent.right = null;
            }
            return;
        }
        //如果是有两个子树的节点
        if(target.left!=null && target.right!=null){
            //让右边的最小值来代替target
            int i = deleteMin(target.right);
            Node newTarget = new Node(i);
            if(parent.left == target){
                parent.left = newTarget;
            }else {
                parent.right = newTarget;
            }
            newTarget.left = target.left;
            newTarget.right = target.right;
            return;
        }
        //否则就是只有一颗子树的情况
        if(parent.left == target){
            if(target.left != null){
                parent.left = target.left;
            }else {
                parent.left = target.right;
            }
        }else {
            if(target.left!=null){
                parent.right = target.left;
            }else {
                parent.right = target.right;
            }
        }

    }

    //编写方法根据传入的值找到它的父节点返回
    public Node getParent(int val){
        //思路分析,根据大小找
        //如果是根节点,则没有父节点
        if(root == null || root.value == val){
            return null;
        }
        //如果根节点就是父节点
        if(root.right!=null && root.right.value==val || root.left!=null&&root.left.value==val){
            return root;
        }
        //递归查找
        return root.getParent(val);
    }

    //编写方法根据传入的节点找到它的父节点并返回
    public Node getParent(Node node){
        //思路分析,根据大小找
        //如果是根节点,则没有父节点
        if(root == null || root == node){
            return null;
        }
        //如果根节点就是父节点
        if(root.right!=null&&root.right==node || root.left!=null&&root.left==node){
            return root;
        }
        //递归查找
        return root.getParent(node);
    }

    //编写方法找到根据节点找到它的子树的最小值节点删除并返回其值
    public int deleteMin(Node node){
        //不断向左找,最有一定就是最小值节点(二叉排序树的特点)
        Node curNode = node;
        while (curNode.left!=null){
            curNode = curNode.left;
        }
        //根据值删除该节点
        delete(curNode);
        //返回它的值
        return curNode.value;
    }

    //编写方法根据传入的值找到它对应的节点
    public Node searchNode(int val){
        //先判断是否空
        if(root == null){
            return null;
        }
        return root.searchNode(val);
    }

    //编写方法中序遍历二叉树
    public void infixOrder(){
        //先判断是否树空
        if(root == null){
            System.out.println("该排序二叉树空");
            return;
        }
        //中序遍历
        root.infixOrder();
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}

/**
 * Node节点类
 */
class Node{
    int value;//值
    Node left;
    Node right;

    //构造器
    public Node(int value){
        this.value = value;
    }

    //编写方法实现添加节点
    public void add(Node node){
        //思路分析:二叉排序树的节点添加,要保持添加之后有序
        //过程: 让要加入的节点跟自己比较,
        // 如果小于自己,递归加到左边,如果左边为空则直接挂到左边
        // 否则大于自己,递归加到右边,如果右边为空则直接挂到右边
        //先判断是否传入空
        if(node == null){
            return;
        }
        //判断后添加
        if(node.value < this.value){
            //如果小于
            if(left == null){
                left = node;
            }else {
                left.add(node);
            }
        }else {
            //否则大于等于
            if(right == null){
                right = node;
            }else {
                right.add(node);
            }
        }
    }

    //编写方法递归查找指定值的父节点
    public Node getParent(int val){
        //根据val的值递归查找
        //先判断自己是不是
        if(right!=null && right.value == val || left!=null&&left.value ==val){
            return this;
        }
        //如果大于,右边找
        if(val>value&&right!=null){
            return right.getParent(val);
        }
        //如果小于,左边找
        if(val<value&&left!=null){
            return left.getParent(val);
        }
        //如果都没有,说明没找到
        return null;
    }

    //编写方法根据传入的节点查找它的父节点
    public Node getParent(Node node){
        //根据val的值递归查找,判断是用节点判断
        //先判断自己是不是
        if(right!=null && right== node || left!=null&&left ==node){
            return this;
        }
        //如果大于,右边找
        if(node.value>value&&right!=null){
            return right.getParent(node);
        }
        //如果小于,左边找
        if(node.value<value&&left!=null){
            return left.getParent(node);
        }
        //如果都没有,说明没找到
        return null;
    }

    //编写方法递归查找指定值的节点
    public Node searchNode(int val){
        //判断自己是不是
        if(val == value){
            return this;
        }
        //如果大于
        if(val>value&&right!=null){
            return right.searchNode(val);
        }
        //如果小于
        if(val<value&&left!=null){
            return left.searchNode(val);
        }
        //如果都没有找到
        return null;
    }

    //编写方法中序遍历二叉树
    public void infixOrder(){
        //中序遍历: 左递归 -----> 自己 -----> 右递归
        //左递归
        if(left!=null){
            left.infixOrder();
        }
        //自己
        System.out.println(this);
        //右递归
        if(right!=null){
            right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}